package algorithm.array;

/**
 * leetcode : https://leetcode.com/problems/minimum-size-subarray-sum/description/
 * 209.Minimum Size Subarray Sum
 * Difficulty : Medium
 *
 * 给一个正整数组，和一个正数s
 * 找到最短的子数组，使得子数组的和 >= s
 * 如果没有结果则返回0
 *
 * 举栗：
 * Input: s = 7, nums = [2,3,1,2,4,3]
 * Output: 2
 * 满足条件的最短子数组是 [4,3]
 *
 * @Author Antony
 * @Since 2018/7/27 19:29
 */
public class MinimunSizeSubArraySum {

    public static void main(String[] args) {
        int[] arr = new int[]{7,3,1,1,4,3};
        int s = 7;
        System.out.println(minSubArrayLen(s, arr));
        System.out.println(minSubArrayLen_clean(s, arr));
    }


    /**
     * beats 99.92% - 2ms
     */
    public static int minSubArrayLen_clean(int s, int[] nums) {
        if(nums.length == 0) return 0;
        int sum = 0;
        int min = nums.length + 1;
        int i = 0;
        int j = 0;
        while(j < nums.length){
            sum += nums[j];
            while(sum >= s){
                int tmpLen = j - i + 1;
                min = tmpLen < min ? tmpLen : min;
                sum -= nums[i];
                i++;
            }
            j++;
        }
        return min==nums.length+1 ? 0 : min;
    }

    /**
     * beats 99.92% - 2ms
     *
     * 实现的并不优雅，判断条件限定太多。思考如何优化减少代码量
     *
     * 思路：双指针
     * 并且一个tmpSum 记录指针间数字的和，避免重复计算 DP的思路
     */
    public static int minSubArrayLen(int s, int[] nums) {
        if(nums.length == 0) return 0;
        int tmpSum = nums[0];
        int minLength = 0;
        int startIndex = 0;
        int endIndex = 0;
        while(endIndex < nums.length && startIndex <= endIndex){
            if(tmpSum < s){
                if(endIndex == nums.length-1) break;
                endIndex++;
                tmpSum += nums[endIndex];
            }else{
                int tmpLength = endIndex - startIndex + 1;
                if(minLength==0){
                    minLength = tmpLength;
                }else{
                    minLength = tmpLength < minLength ? tmpLength : minLength;
                }
                tmpSum -= nums[startIndex];
                startIndex++;
            }
        }

        return minLength;
    }


    /**
     * 2ms, 82.29%
     * @param s
     * @param nums
     * @return
     */
    public static int minSubArrayLen_test(int s, int[] nums) {
        int sIdx = 0;
        int eIdx = 0;
        int sum = 0;
        int minLen = nums.length+1;
        while(eIdx < nums.length){
            sum +=nums[eIdx++];
            while(sum >= s){
                minLen = Math.min(eIdx-sIdx, minLen);
                sum -=nums[sIdx++];
            }
        }
        return minLen==nums.length+1 ? 0 : minLen;
    }
}
